#!/usr/bin/env python
# -*-coding:utf-8-*-

def levenshtein(stra, strb):
    lena = len(stra)
    lenb = len(strb)
    d_old = [i for i in range(lena + 1)]
    d_new = [0] * (lena + 1)

    for i in range(lenb):
        d_new[0] = i
        for j in range(lena):
            if strb[i ] == stra[j]:
                d_new[j + 1] = d_old[j]
            else:
                d_new[j + 1] = min(d_old[j], d_old[j + 1], d_new[j]) + 1
        d_old = d_new
        d_new = [0] * (lena + 1)

    return d_old[-1]

def levenshtein_max(stra, strb, max_dis):
    lena = len(stra)
    lenb = len(strb)
    if abs(lena - lenb) > max_dis:
        return -1

    d_old = [i for i in range(lena + 1)]
    d_new = [0] * (lena + 1)
    for i in range(lenb):
        d_new[0] = i
        for j in range(lena):
            if strb[i] == stra[j]:
                d_new[j+1] = d_old[j]
            else:
                d_new[j+1] = min(d_old[j], d_old[j+1], d_new[j]) + 1
            if d_new[j + 1] > j - i and i - j > max_dis:
                return  -1
        d_old = d_new
        d_new = [0] * (lena + 1)
    return d_old[-1]

